package day_2022_4_to_7.nowcoder;

/**
 * 二进制中1的个数
 * @author haomin
 * @date 2022/04/14 11:08
 **/
public class NumberOf1_9f {
    public static void main(String[] args) {
        System.out.println(NumberOf1_1(2147483647));
        System.out.println(NumberOf1_2(2147483647));
        System.out.println(NumberOf1_3(2147483647));
    }

    // 错解
    // 从n的2进制形式的最右边开始判断是不是1
    // 可能陷入死循环的解法
    // 因为负数右移时，在最高位补得是1
    public static int NumberOf1_1(int n) {
        int count = 0;
        while (n != 0){
            if((n & 1) == 1){
                count ++;
            }
            // 把n的2进制形式往右推一位
            n = n >> 1;
        }
        return count;
    }

    // 方法一：
    // 和错解类似，只是我们现在将1左移一位
    public static int NumberOf1_2(int n) {
        int count = 0;
        int flag = 1;
        while (flag != 0){
            if((n & flag) != 0){
                count ++;
            }
            flag = flag << 1;
        }
        return count;
    }

    // 方法二：
    // 例：    1000 1010   (n)
    //        1000 1001   (n-1)
    //   &之后 1000 1000   排除了一个1
    // 所以我们可以不停的n & (n-1)，直到n == 0000 0000，排除结束
    public static int NumberOf1_3(int n) {
        int count = 0;
        while (n != 0){
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}